package BackTracking;

import java.util.Arrays;

import static java.lang.Float.POSITIVE_INFINITY;

/**
 * 旅行商问题
 * 排列树
 *
 * @author: luo
 * @email: luo@nyist.edu.cn
 * @date: 2020/12/26 11:14
 */
public class TSP {

    public static void main(String[] args) {
        traveling(2);
        System.out.println(bestl);
        for (int i = 1; i <= n; i++) {
            System.out.print(bestx[i] + "->");
        }
    }

    static int n = 5;
    static final int NoEdge = 0;
    static int[] bestx = new int[n + 1];
    static int[][] G = {{-1, -1, -1, -1, -1, -1},
            {-1, -1, 10, -1, 4, 12},
            {-1, 10, -1, 15, 8, 5},
            {-1, -1, 15, -1, 7, 30},
            {-1, 4, 8, 7, -1, 6},
            {-1, 12, 5, 30, 6, -1}};//a[i][j]≠-1表示城市i和城市j有边相连
    static int bestl = 1024; // 当前最短路径
    static int cl = 0; //已经走过的路径长度
    static int[] x = {0, 1, 2, 3, 4, 5};//解空间

    /**
     *  解空间：排列树
     *  约束条件：城市i和城市j有边相连
     *  限界条件：cl < bestl
     * @param t
     */
    static void traveling(int t) {
        if (t > n) {
            // 到达叶子节点
            if (G[x[n]][x[1]] != NoEdge && (cl + G[x[n]][x[1]] < bestl)) {
                for (int i = 1; i <= n; i++) {
                    bestx[i] = x[i];
                }
                bestl = cl + G[x[n]][1];
            }
        } else {//没有到达叶子节点
            //控制当前节点的分支数目，即对x[t]的所有可能的取值。
            for (int j = t; j <= n; j++) {
                if (G[x[t - 1]][x[j]] != NoEdge && (cl + G[x[t - 1]][x[j]] < bestl)) {
                    //保存第t个要去的城市编号到x[t]中，进入到第t+1层
                    swap(t, j); //交换两个元素的值
                    cl += G[x[t - 1]][x[j]];
                    //从第t+1层的扩展结点继续搜索
                    traveling(t + 1);
                    //第t+1层搜索完毕，回溯到第t层
                    cl -= G[x[t - 1]][x[j]];
                    swap(t, j);
                }
            }
        }

    }


    static void swap(int a, int b) {
        int c = x[a];
        x[a] = x[b];
        x[b] = c;
    }

}
